package com.gjh.study.basic.datastructure.tree;

import java.util.*;

/**
 * @author guangjh
 * @version 1.0
 * @date 2020/7/15 9:56
 */
public class BinaryTree {
    static ArrayList<Integer> preList = new ArrayList<>();

    /**
     * 前序遍历：递归法
     *
     * @param root
     * @return
     */
    public List<Integer> preOrder(TreeNode root) {
        if (root == null) {
            return preList;
        }
        preList.add(root.value);
        preOrder(root.leftNode);
        preOrder(root.rightNode);
        return preList;
    }

    /**
     * 前序遍历：迭代法，借助栈
     *
     * @param root
     * @return
     */
    public List<Integer> preOrder2(TreeNode root) {
        List<Integer> preList2 = new ArrayList<>();
        if (root == null) {
            return preList2;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode temp = stack.pop();
            preList2.add(temp.value);
            if (temp.rightNode != null) {
                stack.push(temp.rightNode);
            }
            if (temp.leftNode != null) {
                stack.push(temp.leftNode);
            }
        }
        return preList2;
    }

    static List<Integer> midList = new ArrayList<>();

    /**
     * 中序遍历：递归法
     * 添加某个元素前要添加它的所有左节点
     *
     * @param root
     * @return
     */
    public List<Integer> midOrder(TreeNode root) {
        if (root == null) {
            return midList;
        }
        midOrder(root.leftNode);
        midList.add(root.value);
        midOrder(root.rightNode);
        return midList;
    }

    /**
     * 中序遍历：迭代法，借助栈
     *
     * @param root
     * @return
     */
    public List<Integer> midOrder2(TreeNode root) {
        List<Integer> midList2 = new ArrayList<>();
        if (root == null) {
            return midList;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                node = node.leftNode;
            }
            node = stack.pop();
            midList2.add(node.value);
            node = node.rightNode;
        }
        return midList2;
    }

    static List<Integer> postList = new ArrayList<>();

    /**
     * 后序遍历：递归法
     *
     * @param root
     * @return
     */
    public List<Integer> postOrder(TreeNode root) {
        if (root == null) {
            return postList;
        }
        postOrder(root.leftNode);
        postOrder(root.rightNode);
        postList.add(root.value);
        return postList;
    }

    /**
     * 层序遍历：迭代法，借助队列
     *
     * @param root
     * @return
     */
    public List<Integer> levelOrder(TreeNode root) {
        List<Integer> levelList = new ArrayList<>();
        if (root == null) {
            return levelList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            if (temp != null) {
                levelList.add(temp.value);
            }
            if (temp.leftNode != null) {
                queue.offer(temp.leftNode);
            }
            if (temp.rightNode != null) {
                queue.offer(temp.rightNode);
            }
        }
        return levelList;
    }

    /**
     * 层序遍历，逐行打印：迭代法， 借助队列
     *
     * @param root
     */
    public void levelOrder2(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        int count = queue.size();
        queue.offer(root);
        while (!queue.isEmpty()) {
            if (count == 0) {
                count = queue.size();
            }
            TreeNode temp = queue.poll();
            if (temp != null) {
                count--;
                System.out.print(temp.value + " ");
            }
            if (count == 0) {
                System.out.println();
            }
            if (temp.leftNode != null) {
                queue.offer(temp.leftNode);
            }
            if (temp.rightNode != null) {
                queue.offer(temp.rightNode);
            }
        }
    }

    /**
     * Z 字型遍历：迭代法，借助栈
     * 奇数从左向右遍历，偶数从右向左遍历
     * @param root
     * @return
     */
    public List<Integer> zOrder(TreeNode root) {
        List<Integer> zList = new ArrayList<>();
        if (root == null) {
            return zList;
        }
        // 负责奇数层
        Stack<TreeNode> s1 = new Stack<>();
        // 负责偶数层
        Stack<TreeNode> s2 = new Stack<>();

        s1.push(root);

        while (!s1.empty() || !s2.empty()) {
            while (!s1.empty()) {
                TreeNode temp = s1.pop();
                zList.add(temp.value);
                // 交替进行
                if (temp.leftNode != null) {
                    s2.push(temp.leftNode);
                }
                if (temp.rightNode != null) {
                    s2.push(temp.rightNode);
                }
            }
            while (!s2.empty()) {
                TreeNode temp = s2.pop();
                zList.add(temp.value);
                if (temp.rightNode != null) {
                    s1.push(temp.rightNode);
                }
                if (temp.leftNode != null) {
                    s1.push(temp.leftNode);
                }
            }
        }
        return zList;
    }

    public int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = getDepth(root.leftNode);
        int rightDepth = getDepth(root.rightNode);
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }

    /**
     * 将有序数组重建为二叉排序树
     * 有序数组实际上是中序遍历的结果
     * @param array
     * @param start
     * @param end
     * @return
     */
    public TreeNode convert(int[] array, int start, int end) {
        if (array == null || start > end) {
            return null;
        }
        int middle = (start + end) / 2;
        TreeNode root = new TreeNode(array[middle]);
        root.setLeftNode(convert(array, start, middle - 1));
        root.setRightNode(convert(array, middle + 1, end));
        return root;
    }
}
